package C057;

import java.util.Arrays;

/**
 * ClassName: c03
 * Package: C057
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/5/2 10:57
 * @Version 1.0
 * @Since 1.0
 */
public class c03 {
    public static void main(String[] args) {

//        int[] vals1 = { 2, 1, 1, 2, 2, 1, 1, 2 };
//        int[][] edges1 = {
//                { 0, 1 },
//                { 0, 2 },
//                { 1, 3 },
//                { 2, 4 },
//                { 2, 5 },
//                { 5, 6 },
//                { 6, 7 } };
//        System.out.println(numberOfGoodPaths(vals1, edges1));
//
//        int[] vals2 = {1, 2, 2, 3, 1, 2, 2, 1, 1, 3, 3, 3, 3};
//        int[][] edges2 = {
//                {0, 1},
//                {0, 2},
//                {0, 3},
//                {1, 4},
//                {4, 7},
//                {4, 8},
//                {3, 5},
//                {3, 6},
//                {6, 9},
//                {6, 10},
//                {6, 11},
//                {9, 12}};
//        System.out.println(numberOfGoodPaths(vals2, edges2));
//

        int[] vals3 = {1,3,2,1,3};
        int[][] edges3 = {{0,1},{0,2},{2,3},{2,4}};
        System.out.println(numberOfGoodPaths(vals3, edges3));
    }


    static int MAXLEN = 10000;
    static int[] father = new int[MAXLEN];
    static int[] maxcnt = new int[MAXLEN];


    public static int numberOfGoodPaths(int[] vals, int[][] edges) {
        build(vals.length);
        // 边排序
        Arrays.sort(edges, (a1, a2) -> {
            return Math.max(vals[a1[0]], vals[a1[1]]) - Math.max(vals[a2[0]], vals[a2[1]]);
        });

        // 求答案
        int ans = vals.length;
        for (int i = 0; i < edges.length; i++) {
            ans += union(edges[i][0], edges[i][1], vals);
        }
        return ans;
    }


    // 合并元素
    private static int union(int i, int j, int[] vals) {
        int fatheri = find(i);
        int fatherj = find(j);
        if (fatheri == fatherj) {
            return 0;
        }
        int path = 0;
        if (vals[father[fatheri]] > vals[father[fatherj]]) {
            father[fatherj] = fatheri;
        } else if (vals[father[fatheri]] < vals[father[fatherj]]) {
            father[fatheri] = fatherj;
        } else {
            father[fatheri] = fatherj;
            path = maxcnt[fatheri] * maxcnt[fatherj];
            maxcnt[fatherj] += maxcnt[fatheri];

        }

        return path;

    }

    private static int find(int i) {
        if (father[i] == i) {
            return i;
        }
        father[i] = find(father[i]);
        return father[i];
    }

    private static void build(int length) {
        // 1 构建并查集
        for (int i = 0; i < length; i++) {
            father[i] = i;
            maxcnt[i] = 1;
        }
    }
}
